﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using System.Diagnostics.Contracts;

namespace SimpleIR
{
	/// <summary>
	/// A representation for interning and tracking all the program type signatures.
	/// </summary>
	public sealed class IRTypeTable
	{
		/////////////
		//special types that are handy to have quick references to
		
		private readonly IRPtrType m_nullPtrType;
		private readonly IRVoidType m_voidType;

		private IRClassType m_rootObjectType;
		private IRClassType m_stringObjectType;

		private IRNumericType m_numericstackvalue;

		private IRSignedIntegerType m_booltype;
		private IRUnSignedIntegerType m_chartype;
		
		private IRSignedIntegerType m_int8type;
		private IRUnSignedIntegerType m_uint8type;
		private IRSignedIntegerType m_int16type;
		private IRUnSignedIntegerType m_uint16type;
		private IRSignedIntegerType m_int32type;
		private IRUnSignedIntegerType m_uint32type;
		private IRSignedIntegerType m_int64type;
		private IRUnSignedIntegerType m_uint64type;

		private IRFloatingPointType m_float32type;
		private IRFloatingPointType m_float64type;

		private IRFunctionPointerType m_funcptrtype;

		//map from a type to the pointer to that type
		private readonly Dictionary<IRType, IRPtrType> m_typeToPtrMap;

		//map from a type to the reference to that type
		private readonly Dictionary<IRType, IRReferenceType> m_typeToReferenceMap;

		//map from a type to the boxed version of that type
		private readonly Dictionary<IRType, IRBoxedType> m_typeToBoxedTypeMap;

		//Internal table for types
		private readonly Dictionary<String, IRType> m_typeInternTable;

		[ContractInvariantMethod]
		private void ObjectInvariant()
		{
			Contract.Invariant(this.m_nullPtrType != null);
			Contract.Invariant(this.m_voidType != null);
			
			Contract.Invariant(this.m_typeToPtrMap != null);
			Contract.Invariant(this.m_typeToReferenceMap != null);
			Contract.Invariant(this.m_typeToBoxedTypeMap != null);
			Contract.Invariant(this.m_typeInternTable != null);
		}

		public IRTypeTable()
		{
			this.m_typeInternTable = new Dictionary<String, IRType>();
			this.m_typeToPtrMap = new Dictionary<IRType, IRPtrType>();
			this.m_typeToReferenceMap = new Dictionary<IRType, IRReferenceType>();
			this.m_typeToBoxedTypeMap = new Dictionary<IRType, IRBoxedType>();

			this.m_nullPtrType = IRPtrType.MakeSpecialNullPtr();
			this.InternNewType(this.m_nullPtrType);

			this.m_voidType = new IRVoidType();
			this.InternNewType(this.m_voidType);
		}

		/// <summary>
		/// Load a number of useful constants.
		/// </summary>
		public void SetSpecialTypes()
		{
			this.m_rootObjectType = (IRClassType)this.m_typeInternTable["System.Object"];
			this.m_stringObjectType = (IRClassType)this.m_typeInternTable["System.String"];

			this.m_numericstackvalue = (IRNumericType)this.m_typeInternTable["System.NumericStackValue"];

			this.m_booltype = (IRSignedIntegerType)this.m_typeInternTable["System.Boolean"];
			this.m_chartype = (IRUnSignedIntegerType)this.m_typeInternTable["System.Char"];
			this.m_int8type = (IRSignedIntegerType)this.m_typeInternTable["System.SByte"];
			this.m_uint8type = (IRUnSignedIntegerType)this.m_typeInternTable["System.Byte"];
			this.m_int16type = (IRSignedIntegerType)this.m_typeInternTable["System.Int16"];
			this.m_uint16type = (IRUnSignedIntegerType)this.m_typeInternTable["System.UInt16"];
			this.m_int32type = (IRSignedIntegerType)this.m_typeInternTable["System.Int32"];
			this.m_uint32type = (IRUnSignedIntegerType)this.m_typeInternTable["System.UInt32"];
			this.m_int64type = (IRSignedIntegerType)this.m_typeInternTable["System.Int64"];
			this.m_uint64type = (IRUnSignedIntegerType)this.m_typeInternTable["System.UInt64"];

			this.m_float32type = (IRFloatingPointType)this.m_typeInternTable["System.Single"];
			this.m_float64type = (IRFloatingPointType)this.m_typeInternTable["System.Double"];

			this.m_funcptrtype = (IRFunctionPointerType)this.m_typeInternTable["System.FunctionPtr"];

			this.m_typeInternTable.Add("System.IntPtr", this.m_funcptrtype);
		}

		/// <summary>
		/// Return true if the given type name is already interned
		/// </summary>
		[Pure]
		internal bool IsTypeNameInterned(String tn)
		{
			Contract.Requires(!String.IsNullOrEmpty(tn));

			return this.m_typeInternTable.ContainsKey(tn); 
		}

		/// <summary>
		/// Intern a new type with the given name (as needed).
		/// </summary>
		internal void InternNewType(IRType tt)
		{
			Contract.Requires(tt != null && (!this.IsTypeNameInterned(tt.TypeName)));

			this.m_typeInternTable.Add(tt.TypeName, tt);

			if(tt is IRPtrType)
			{
				IRPtrType pty = (IRPtrType)tt;
				if(!pty.IsNullPointer)
					this.m_typeToPtrMap.Add(pty.PtrTargetType, pty);
			}

			if(tt is IRReferenceType)
			{
				IRReferenceType rty = (IRReferenceType)tt;
				this.m_typeToReferenceMap.Add(rty.ReferenceTargetType, rty);
			}

			if(tt is IRBoxedType)
				this.m_typeToBoxedTypeMap.Add(((IRBoxedType)tt).BoxedTypeValue, (IRBoxedType)tt);
		}

		/// <summary>
		/// Lookup (creating if needed) the pointer type for a given base type.
		/// </summary>
		public IRPtrType InternPointerTypeFor(IRType tt)
		{
			Contract.Requires(tt != null);
			Contract.Ensures(Contract.Result<IRPtrType>() != null);

			if(!this.m_typeToPtrMap.ContainsKey(tt))
			{
				IRType rtt = new IRPtrType(tt.NameSpaceScope, tt.BaseTypeName + "*", (TypeQualifiers.PublicTag | TypeQualifiers.BuiltinTag), tt);
				this.InternNewType(rtt);
			}
			return this.m_typeToPtrMap[tt];
		}

		/// <summary>
		/// Lookup the pointer type for a given base type.
		/// </summary>
		[Pure]
		public IRPtrType LookupPointerTypeFor(IRClassType tt)
		{
			Contract.Requires(tt != null);
			Contract.Ensures(Contract.Result<IRPtrType>() != null);

			return this.m_typeToPtrMap[tt]; 
		}

		/// <summary>
		/// Lookup (creating if needed) the reference type for a given base type.
		/// </summary>
		public IRReferenceType InternReferenceTypeFor(IRType tt)
		{
			Contract.Requires(tt != null);
			Contract.Ensures(Contract.Result<IRReferenceType>() != null);

			if(!this.m_typeToReferenceMap.ContainsKey(tt))
			{
				IRType rtt = new IRReferenceType(tt.NameSpaceScope, tt.BaseTypeName + "&", (TypeQualifiers.PublicTag | TypeQualifiers.BuiltinTag), tt);
				this.InternNewType(rtt);
			}
			return this.m_typeToReferenceMap[tt];
		}

		/// <summary>
		/// Lookup the pointer type for a given base type.
		/// </summary>
		[Pure]
		public IRReferenceType LookupReferenceTypeFor(IRType tt)
		{
			Contract.Requires(tt != null);
			Contract.Ensures(Contract.Result<IRReferenceType>() != null);

			return this.m_typeToReferenceMap[tt];
		}

		/// <summary>
		/// Lookup (creating if needed) the boxed type for a given valuetype.
		/// </summary>
		public IRBoxedType InternBoxedTypeFor(IRValueType tt)
		{
			Contract.Requires(tt != null);
			Contract.Ensures(Contract.Result<IRBoxedType>() != null);

			if(!this.m_typeToBoxedTypeMap.ContainsKey(tt))
			{
				IRBoxedType rtt = new IRBoxedType(tt.NameSpaceScope, tt.BaseTypeName + "|Box", (TypeQualifiers.PublicTag | TypeQualifiers.BuiltinTag), tt);
				this.InternNewType(rtt);
			}
			return this.m_typeToBoxedTypeMap[tt];
		}

		/// <summary>
		/// Lookup the boxed type for a given base value type.
		/// </summary>
		[Pure]
		public IRBoxedType LookupBoxedTypeFor(IRValueType tt)
		{
			Contract.Requires(tt != null);
			Contract.Ensures(Contract.Result<IRBoxedType>() != null);

			return this.m_typeToBoxedTypeMap[tt]; 
		}

		/// <summary>
		/// Lookup a type for a name if we know the type must exist.
		/// </summary>
		[Pure]
		public IRType LookupTypeForName(String tn)
		{
			Contract.Requires(!String.IsNullOrEmpty(tn));
			Contract.Ensures(Contract.Result<IRType>() != null);

			return this.m_typeInternTable[tn]; 
		}

		/// <summary>
		/// Lookup a type for a name return the type or null if it doesn't exist.
		/// </summary>
		public IRType LookupTypeForNameOrNull(String tn)
		{
			Contract.Requires(!String.IsNullOrEmpty(tn));

			if(!this.m_typeInternTable.ContainsKey(tn))
				return null;
			else
				return this.m_typeInternTable[tn];
		}

		/////////////////
		//Get handy types

		public IRClassType RootObjectType 
		{ 
			get 
			{
				Contract.Ensures(Contract.Result<IRClassType>() != null);

				return this.m_rootObjectType; 
			} 
		}

		public IRClassType StringObjectType 
		{ 
			get 
			{
				Contract.Ensures(Contract.Result<IRClassType>() != null);

				return this.m_stringObjectType; 
			} 
		}

		public IRPtrType NullType 
		{ 
			get 
			{
				Contract.Ensures(Contract.Result<IRPtrType>() != null);

				return this.m_nullPtrType; 
			} 
		}
		
		public IRVoidType VoidType 
		{ 
			get 
			{
				Contract.Ensures(Contract.Result<IRVoidType>() != null);

				return this.m_voidType; 
			} 
		}

		public IRFunctionPointerType FunctionPtrType
		{
			get
			{
				Contract.Ensures(Contract.Result<IRFunctionPointerType>() != null);

				return this.m_funcptrtype;
			}
		}

		public IRNumericType NumericStackValueType
		{
			get
			{
				Contract.Ensures(Contract.Result<IRNumericType>() != null);

				return this.m_numericstackvalue;
			}
		}

		public IRSignedIntegerType BoolType
		{
			get
			{
				Contract.Ensures(Contract.Result<IRSignedIntegerType>() != null);

				return this.m_booltype;
			}
		}

		public IRUnSignedIntegerType CharType
		{
			get
			{
				Contract.Ensures(Contract.Result<IRUnSignedIntegerType>() != null);

				return this.m_chartype;
			}
		}

		public IRSignedIntegerType Int8Type
		{
			get
			{
				Contract.Ensures(Contract.Result<IRSignedIntegerType>() != null);

				return this.m_int8type;
			}
		}

		public IRUnSignedIntegerType UInt8Type
		{
			get
			{
				Contract.Ensures(Contract.Result<IRUnSignedIntegerType>() != null);

				return this.m_uint8type;
			}
		}

		public IRSignedIntegerType Int16Type
		{
			get
			{
				Contract.Ensures(Contract.Result<IRSignedIntegerType>() != null);

				return this.m_int16type;
			}
		}

		public IRUnSignedIntegerType UInt16Type
		{
			get
			{
				Contract.Ensures(Contract.Result<IRUnSignedIntegerType>() != null);

				return this.m_uint16type;
			}
		}

		public IRSignedIntegerType Int32Type
		{
			get
			{
				Contract.Ensures(Contract.Result<IRSignedIntegerType>() != null);

				return this.m_int32type;
			}
		}

		public IRUnSignedIntegerType UInt32Type 
		{
			get 
			{
				Contract.Ensures(Contract.Result<IRUnSignedIntegerType>() != null);

				return this.m_uint32type; 
			} 
		}

		public IRSignedIntegerType Int64Type
		{
			get
			{
				Contract.Ensures(Contract.Result<IRSignedIntegerType>() != null);

				return this.m_int64type;
			}
		}

		public IRUnSignedIntegerType UInt64Type
		{
			get
			{
				Contract.Ensures(Contract.Result<IRUnSignedIntegerType>() != null);

				return this.m_uint64type;
			}
		}

		public IRFloatingPointType Float32Type
		{
			get
			{
				Contract.Ensures(Contract.Result<IRFloatingPointType>() != null);

				return this.m_float32type;
			}
		}

		public IRFloatingPointType Float64Type
		{
			get
			{
				Contract.Ensures(Contract.Result<IRFloatingPointType>() != null);

				return this.m_float64type;
			}
		}

		/// <summary>
		/// This is only valid AFTER the load of the entire program.
		/// </summary>
		public IRMemberField RootObjectRTTIField
		{
			get
			{
				Contract.Assert(this.m_rootObjectType.TypeDescription.AllDefInFields.Count == 1);

				return this.m_rootObjectType.TypeDescription.AllDefInFields[0];
			}
		}

		/// <summary>
		/// Return a COPIED list of all the types defined in the program.
		/// This has poor performance so only use it during initialization and output phases.
		/// </summary>
		public List<IRType> AllDefinedTypes
		{ get { return new List<IRType>(this.m_typeInternTable.Values); } }

		/////////////////////////////////////////////////
		//Code for computing the closures of the type information we need

		/// <summary>
		/// Complete the computation of the boxed types
		/// </summary>
		internal void ComputeAllBoxedTypeInfo(IRIdentifierTable mft)
		{
			Contract.Requires(mft != null);

			foreach(KeyValuePair<IRType, IRBoxedType> ttp in this.m_typeToBoxedTypeMap)
			{
				IRMemberField ff = ttp.Value.TypeDescription.LoadFieldInfoAsNeeded(ttp.Value, "data", ttp.Key, SpecialFieldTag.NormalField, FieldQualifiers.PublicTag);
				
				IRBoxedType btt = ttp.Value;
				IRType vtt = btt.BoxedTypeValue;

				btt.TypeDescription.AllInheritsExtends.UnionWith(vtt.TypeDescription.AllInheritsExtends);
				btt.TypeDescription.AllSubTypes.Add(btt);
				
				btt.TypeDescription.AllVisibleFields.Add(ff);
				btt.ProcessBuiltinInfoAsNeeded();
			}
		}

		/// <summary>
		/// Complete the reference and pointer types information.
		/// </summary>
		internal void CompleteRefAndPointerTypeInfo()
		{
			List<IRClassType> cllt = new List<IRClassType>();
			foreach(IRType tt in this.m_typeInternTable.Values)
			{
				if(tt is IRClassType)
					cllt.Add((IRClassType)tt);
			}

			foreach(IRClassType btt in cllt)
				this.InternPointerTypeFor(btt);
			
			List<IRType> ott = new List<IRType>();
			foreach(IRType tt in this.m_typeInternTable.Values)
			{
				if(!(tt is IRReferenceType))
					ott.Add(tt);
			}

			foreach(IRType tt in ott)
				this.InternReferenceTypeFor(tt);
		}

		/// <summary>
		/// Compute all classes (including this) that in some way inherit from this.
		/// This should be the first step after loading the program assembly.
		/// </summary>
		internal void ComputeAllChildClasses()
		{
			Dictionary<IRType, HashSet<IRType>> subtydict = new Dictionary<IRType, HashSet<IRType>>();
			foreach(IRType tt in this.m_typeInternTable.Values)
			{
				Contract.Assert(!subtydict.ContainsKey(tt) || (tt is IRFunctionPointerType));

				if(!subtydict.ContainsKey(tt))
				{
					subtydict.Add(tt, new HashSet<IRType>());
					subtydict[tt].Add(tt);
				}
			}

			foreach(IRType tt in this.m_typeInternTable.Values)
			{
				foreach(IRType ihft in tt.TypeDescription.AllInheritsExtends)
				{
					if(tt is IRNumericType || tt is IRStructType)
						subtydict[ihft].Add(this.m_typeToBoxedTypeMap[(IRValueType)tt]);
					
					subtydict[ihft].Add(tt);
				}
			}

			bool changing = true;
			while(changing)
			{
				changing = false;
				foreach(IRType tt in this.m_typeInternTable.Values)
				{
					HashSet<IRType> ttch = subtydict[tt];
					foreach(IRType subtt in subtydict[tt])
					{
						HashSet<IRType> subttch = subtydict[subtt];
						if(!ttch.IsSupersetOf(subttch))
						{
							changing = true;
							ttch.UnionWith(subttch);
							break;
						}
					}
				}
			}

			foreach(IRType tt in this.m_typeInternTable.Values)
			{
				tt.TypeDescription.AllSubTypes.Clear();
				tt.TypeDescription.AllSubTypes.UnionWith(subtydict[tt]);
			}

			foreach(IRType tt in this.m_typeInternTable.Values)
			{
				if(tt.TypeDescription.ExtendsSpecialImplType == null)
				{
					IRType exspt = tt.TypeDescription.AllInheritsExtends.FirstOrDefault((IRType iht) => (iht.TypeDescription.TypeQualifierInfo & TypeQualifiers.SpcializedImplTag) != TypeQualifiers.Clear);
					tt.TypeDescription.ExtendsSpecialImplType = exspt;
				}
			}
		}

		/// <summary>
		/// Now that we have complete inheritance information compute which fields are visible from each class.
		/// This should be step #2.
		/// </summary>
		internal void ComputeAllVisFieldInfo()
		{
			Dictionary<IRType, HashSet<IRMemberField>> fdict = new Dictionary<IRType, HashSet<IRMemberField>>();
			
			//initialize with the fields from this type
			foreach(IRType tt in this.m_typeInternTable.Values)
			{
				Contract.Assert(!fdict.ContainsKey(tt) || (tt is IRFunctionPointerType));

				if(!fdict.ContainsKey(tt))
				{
					fdict.Add(tt, new HashSet<IRMemberField>());
					fdict[tt].UnionWith(tt.TypeDescription.AllVisibleFields);
				}
			}

			foreach(IRType tt in this.m_typeInternTable.Values)
			{
				//look at all the subtypes and get all of the types that this is a subtype of and add their fields.
				foreach(IRType subt in tt.TypeDescription.AllSubTypes)
				{
					if(subt is IRValueType)
						continue;

					fdict[subt].UnionWith(tt.TypeDescription.AllVisibleFields);
				}
			}

			//set the final visible field information
			foreach(IRType tt in this.m_typeInternTable.Values)
			{
				tt.TypeDescription.AllVisibleFields.Clear();
				tt.TypeDescription.AllVisibleFields.UnionWith(fdict[tt]);
			}
		}

		/// <summary>
		/// Now that we have all the inheritance information and the bits on the visible fields we can compute which types may be part of recursive data structures.
		/// This should be step #3.
		/// </summary>
		internal void ComputeRecursiveTypeInfo()
		{
			Dictionary<IRType, HashSet<IRType>> reachTypeMap = new Dictionary<IRType, HashSet<IRType>>();
			Dictionary<IRType, HashSet<IRType>> typeswithrefto = new Dictionary<IRType, HashSet<IRType>>();
			Queue<IRType> proctypes = new Queue<IRType>();

			//initialize each type in the dictionary with the set of types reachable from the fields visible to it
			foreach(IRType tt in this.m_typeInternTable.Values)
			{
				if(!(tt is IRClassType || tt is IRStructType))
					continue;

				if(reachTypeMap.ContainsKey(tt))
					continue;

				reachTypeMap.Add(tt, new HashSet<IRType>());
				proctypes.Enqueue(tt);

				foreach(IRMemberField vpf in tt.TypeDescription.AllVisibleFields)
				{
					IRType ftt = ReadThroughPointerTargets(vpf.FieldType);
					if(ftt is IRClassType || ftt is IRStructType)
					{
						reachTypeMap[tt].UnionWith(ftt.TypeDescription.AllSubTypes);

						foreach(IRType subtt in ftt.TypeDescription.AllSubTypes)
						{
							if(!typeswithrefto.ContainsKey(subtt))
								typeswithrefto.Add(subtt, new HashSet<IRType>());
							typeswithrefto[subtt].Add(tt);
						}
					}
				}
			}

			//do fixpoint, for all reach types from tt look at the reach types from those types and accumulate until a fixpoint is reached
			while(proctypes.Count != 0)
			{
				IRType tt = proctypes.Dequeue();
				int isize = reachTypeMap[tt].Count;

				//for each field compute new rectype sets
				foreach(IRMemberField vpf in tt.TypeDescription.AllVisibleFields)
				{
					IRType ftt = ReadThroughPointerTargets(vpf.FieldType);
					if(ftt is IRClassType || ftt is IRStructType)
						reachTypeMap[tt].UnionWith(reachTypeMap[ftt]);
				}

				if(isize != reachTypeMap[tt].Count)
				{
					HashSet<IRType> mpt = typeswithrefto[tt];
					foreach(IRType nt in mpt)
						proctypes.Enqueue(nt);
				}
			}

			//finally set the recusrsive type information
			foreach(IRType tt in this.m_typeInternTable.Values)
			{
				if(!(tt is IRClassType))
					continue;

				HashSet<IRType> ttrs = reachTypeMap[tt];
				foreach(IRType rtt in ttrs)
				{
					if(!(rtt is IRClassType))
						continue;

					if(reachTypeMap[rtt].Contains(tt) && reachTypeMap[tt].Contains(rtt))
						tt.TypeDescription.AllRecursiveWith.Add(rtt);
				}

				tt.TypeDescription.FinalizeRecInfo();
			}
		}

		/// <summary>
		/// We aren't really interested in pointer types so dereference them until we have a base type.
		/// </summary>
		private static IRType ReadThroughPointerTargets(IRType tt)
		{
			while(tt is IRPtrType)
				tt = ((IRPtrType)tt).PtrTargetType;

			return tt;
		}
	}
}
